package top.lshaci.learning.algorithm;

import java.util.Arrays;

/**
 * BinaryHeap
 * <p>
 * 二叉堆(最小堆: 堆顶元素值最小)
 * <p>
 * 二叉堆的所有节点都存储在数组中
 * <p>
 * 假设父节点的下标是 parent, 那么它的左孩子下标就是 2 * parent + 1, 右孩子下标就是 2 * parent + 2
 *
 * @author liangxu
 */
public class BinaryHeap {

    /**
     * "上浮"调整
     * <p>
     * 当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置
     * <p>
     * 新节点的父节点比新节点大，显然不符合最小堆的性质。于是让新节点“上浮”，和父节点交换位置。
     *
     * @param array 待调整的堆
     */
    public static void upAdjust(int[] array) {
        int childrenIndex = array.length - 1;
        int parentIndex = (childrenIndex - 1) / 2;
        // temp 保存插入的叶子节点值, 用于最后赋值
        int temp = array[childrenIndex];
        while (childrenIndex > 0 && temp < array[parentIndex]) {
            // 无须真正交换, 单向赋值即可
            array[childrenIndex] = array[parentIndex];
            childrenIndex = parentIndex;
            parentIndex = (childrenIndex - 1) / 2;
        }
        array[childrenIndex] = temp;
    }

    /**
     * "下沉"调整
     *
     * @param array       待调整的堆
     * @param parentIndex 要"下沉"的父节点
     * @param length      堆的有效大小
     */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        // temp 保存父节点值, 用于最后的赋值
        int temp = array[parentIndex];
        int childrenIndex = 2 * parentIndex + 1;
        while (childrenIndex < length) {
            // 右孩子存在, 且右孩子小于左孩子
            if (childrenIndex + 1 < length && array[childrenIndex + 1] < array[childrenIndex]) {
                childrenIndex++;
            }
            // 父节点小于孩子节点, 则直接跳出
            if (temp < array[childrenIndex]) {
                break;
            }
            // 父节点大于孩子节点, 无须真正交换, 单向赋值即可
            array[parentIndex] = array[childrenIndex];
            parentIndex = childrenIndex;
            childrenIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 构建堆
     *
     * @param array 待调整的堆
     */
    public static void buildHeap(int[] array) {
        // 从最有一个非叶子节点开始调整, 依次做"下沉"调整
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i, array.length);
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        upAdjust(array);
        System.err.println(Arrays.toString(array));

        array = new int[]{7, 1, 3, 10, 5, 2, 8, 9, 6};
        buildHeap(array);
        System.err.println(Arrays.toString(array));
    }
}
